package com.kevin.Code.LinkNode;

/**
 * @author Vinlee Xiao
 * @Classname MergekSortedLists
 * @Description Leetcode 23. 合并K个升序链表 难度 困难 高频
 * @Date 2021/10/25 20:14
 * @Version 1.0
 */
public class MergekSortedLists {


    /**
     * 自己思路 效率不是很高
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {

        int len = lists.length;

        if (len == 0) {
            return null;
        }
//        if (lists[0] == null) {
//            return null;
//        }

        int maxValue = Integer.MAX_VALUE;
        int maxIndex = Integer.MIN_VALUE;
        //用于保存每一次移动的链表
        ListNode[] move = new ListNode[lists.length];
        //将各个头结点赋值到move数组中
        for (int i = 0; i < lists.length; i++) {
            move[i] = lists[i];
        }
        //遍历每一个链表
        ListNode dummy = new ListNode(-1);
        ListNode moveNode = dummy;

        while (true) {
            //将第一条链表的值暂时赋值为最小值
            int minValue = maxValue;
            int minIndex = maxIndex;
            //常规思路
            for (int i = 0; i < lists.length; i++) {
                //当前结点是否为零
                if (move[i] != null) {
                    if (move[i].val < minValue) {
                        minValue = move[i].val;
                        minIndex = i;
                    }
                }

            }
            //遍历到最后直接跳出循环
            if (minValue == maxValue || maxIndex == minIndex) {
                break;
            }
            //连接最小的结点
            moveNode.next = move[minIndex];
            //连接结点转向下一个结点
            moveNode = moveNode.next;
            //最小的结点向后移动
            move[minIndex] = move[minIndex].next;

        }

        return dummy.next;
    }

    /**
     * 利用分治的思想
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists1(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    /**
     * @param lists
     * @param l
     * @param r
     * @return
     */
    public ListNode merge(ListNode[] lists, int l, int r) {

        if (l == r) {
            return lists[l];
        }
        if (l > r) {

            return null;
        }
        //相当于除2 效率更高
        int mid = (l + r) >> 1;

        return megerTwoList(merge(lists, l, mid), merge(lists, mid + 1, r));
    }


    /**
     * @param a
     * @param b
     * @return
     */
    public ListNode megerTwoList(ListNode a, ListNode b) {

        //
        if (a == null || b == null) {

            return a != null ? a : b;
        }

        ListNode dummy = new ListNode(-1);
        ListNode move = dummy;

        ListNode aNode = a;
        ListNode bNode = b;

        while (aNode != null && bNode != null) {

            if (aNode.val < bNode.val) {
                move.next = aNode;
                aNode = aNode.next;
            } else {
                move.next = bNode;
                bNode = bNode.next;
            }
            move = move.next;
        }
        //将剩余未连接的结点连接到move上
        move.next = aNode != null ? aNode : bNode;

        return dummy.next;
    }

}
